package lsl.leetCode.year2023.test0125;

import lsl.leetCode.test1222.ListNode;

public class test203 {
    public static void main(String[] args) {
        ListNode listNode1 = new ListNode(9);
        ListNode hero2 = new ListNode(1);
        ListNode hero3 = new ListNode(8);
        //创建单链表
        listNode1.next = hero2;
        hero2.next = hero3;
        ListNode listNode = removeElements2(listNode1, 9);
        System.out.println(listNode);
    }

    public static ListNode removeElements(ListNode head, int val) {
        //由于链表的头节点head有可能需要被删除，因此创建哑节点dummyHead
        //令dummyHead.next = head
        //然后遍历链表进行删除操作。最终返回dummyHead.next即为删除操作后的头节点。
        ListNode dummyHead = new ListNode(0);
        dummyHead.next = head;

        //相当于当前指针
        ListNode temp = dummyHead;
        while (temp.next != null) {
            if (temp.next.val == val) {
                temp.next = temp.next.next;
            } else {
                //保留当前节点,当前指针往后移一位
                temp = temp.next;
            }
        }
        return dummyHead.next;
    }

    public static ListNode removeElements2(ListNode head, int val) {
        if(head == null) {
            return head;
        }
        //每次出栈，意味着当前指针往左平移一步，举例：1,2,6 val=6
        head.next = removeElements2(head.next, val);
        // 方法递归到最后节点，head.next=null，head=6 等于val，所以null是返回值
        // 一旦出栈，指针左移，此时 head=2，head.next指向的是返回值，即2->null，即6被删除了
        return head.val == val ? head.next : head;
    }
}
